package algorithm.DivideConquer;

/**
 * 翻转对问题，leetcode上有OJ。
 * 给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
 * 这个问题要求给出翻转对的数量
 * 本问题使用leetcode的填函数式IO
 */
public class ReversePairs {

    public static int MAX=5000;
    public static int[] nums=new int[MAX];
    public static int[] help=new int[MAX];
    /**
     * 很简单的暴力解法
     * @return
     */
    public static int bruteReversePairs(){
        int n=nums.length;
        int count=0;
        for(int j=n-1;j>0;j--){
            for(int i=0;i<j;i++){
                if((long)nums[i]>2*(long)nums[j]) count++;
            }
        }
        return count;
    }

    /**
     * 模仿小和问题自己写一版解法
     * @param l
     * @param r
     * @return
     */
    public static int reversePairs(int l,int r){
        if(l==r) return 0;
        int m=(l+r)/2;
        return reversePairs(l,m)+reversePairs(m+1,r)+merge(l,r,m);
    }
    public static int merge(int l,int r,int m){
        int ans=0;

        //这一种解法过不去
//        for(int i,j=m+1,sum=0;j<=r;j++) {
//            i=l;
//            while(i<=m){
//                i++;
//                if((long)nums[i]>2*(long)nums[j]) sum++;
//            }
//            ans+=sum;
//        }

        //这一种解法可以过
        for (int i = l, j = m + 1; i <= m; i++) {
            while (j <= r && (long) nums[i] > (long) nums[j] * 2) {
                j++;
            }
            ans += j - m - 1;
        }
        int i=l;
        int a=l;
        int b=m+1;
        while(a<=m&&b<=r){
            help[i++]=Math.min(nums[a++],nums[b++]);
        }
        while(a<=m) help[i++]=nums[a++];
        while(b<=r) help[i++]=nums[b++];
        for(i=l;i<=r;i++){
            nums[i]=help[i];
        }
        return ans;
    }
}
